package 滑动窗口;

import java.util.*;

public class No295数据流的中位数 {

    /**
     * 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
     * 例如，
     * [2,3,4] 的中位数是 3
     * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
     * 设计一个支持以下两种操作的数据结构：
     * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
     * double findMedian() - 返回目前所有元素的中位数。
     *
     * 示例：
     * addNum(1)
     * addNum(2)
     * findMedian() -> 1.5
     * addNum(3)
     * findMedian() -> 2
     */

    static class MedianFinder{

        PriorityQueue<Integer> maxHeap;
        PriorityQueue<Integer> minHeap;

        //两个堆:一个大堆+一个小堆
        public MedianFinder() {
            this.maxHeap=new PriorityQueue<>((o1,o2)->o1-o2);
            this.minHeap=new PriorityQueue<>((o1,o2)->o2-o1);
        }

        //我们应该保证,两个堆里的数是漏斗形状的
        //重要概念:最大堆顶元素小于等于最小堆顶元素 max:存的都是小的 min:存的都是比max大的;就形成了漏斗;
        //如何维持这个漏斗呢?先进大堆一圈,然后将大堆顶放入小堆,如果小堆比大堆多,就将小堆顶放入大堆(以免只放大堆)
        public void addNum(int num) {
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
            //min:4个 max:3个 ->min:3个 max:4个 造成max个数永远大于等于min个数
            if(minHeap.size()>maxHeap.size()){
                maxHeap.add(minHeap.poll());
            }
        }

        public double findMedian() {
            int count=maxHeap.size()+minHeap.size();
            double result;
            if(count%2==0){
                result=maxHeap.peek()/2.0+minHeap.peek()/2.0;
            }else{
                //多的那个堆
                result=maxHeap.peek();
            }
            return result;
        }

    }

    public static void main(String[] args) {
        MedianFinder medianFinder=new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        medianFinder.addNum(3);
        medianFinder.addNum(4);
        medianFinder.addNum(5);
        medianFinder.addNum(6);
        medianFinder.addNum(7);
        double result = medianFinder.findMedian();
        System.out.println(result);
    }

}
